package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/happy-number/description/?envType=study-plan-v2&envId=top-interview-150">快乐数(Happy Number)</a>
 * <p>编写一个算法来判断一个数 n 是不是快乐数。</p>
 * <p>
 * 「快乐数」 定义为：
 *     <ul>
 *         <li>对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。</li>
 *         <li>然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。</li>
 *         <li>如果这个过程 结果为 1，那么这个数就是快乐数。</li>
 *     </ul>
 *     如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 19
 *      输出：true
 *      解释：
 *          1^2 + 9^2 = 82
 *          8^2 + 2^2 = 68
 *          6^2 + 8^2 = 100
 *          1^2 + 0^2 + 0^2 = 1
 *
 * 示例 2：
 *      输入：n = 2
 *      输出：false
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 2^31 - 1</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/11 15:17
 */
public class LC0202HappyNumber_S {

    static class Solution {
        /**
         * hash表：用哈希集合检测循环
         */
        public boolean isHappy(int n) {
            // 用于判断是否会出现循环，如果会出现循环则说明为非"快乐数"
            Set<Integer> visited = new HashSet<>();
            // 如果得到1，或者进入循环。终止计算
            while (n != 1 && !visited.contains(n)) {
                // 先把当前数加入到已经遇到过的情况中
                visited.add(n);
                int sum = 0;
                while (n > 0) {
                    int i = n % 10;
                    sum += i * i;
                    n = n / 10;
                }
                n = sum;
            }
            return n == 1;
        }

        /**
         * 快慢指针
         */
        public boolean isHappy2(int n) {
            int slowRunner = n;
            int fastRunner = getNext(n);
            while (fastRunner != 1 && slowRunner != fastRunner) {
                slowRunner = getNext(slowRunner);
                fastRunner = getNext(getNext(fastRunner));
            }
            return fastRunner == 1;
        }

        private int getNext(int n) {
            int sum = 0;
            while (n > 0) {
                int remainder = n % 10;
                sum += remainder * remainder;
                n /= 10;
            }
            return sum;
        }

        public boolean testEquals(int n) {
            return isHappy(n) == isHappy2(n);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            int i1 = random.nextInt(Integer.MAX_VALUE);
            System.out.println(i1);
            if (!solution.testEquals(i1)) {
                System.out.println("出错啦..");
            }
        }
    }
}
